package BinaryTree;
/*
* 二叉树展开为链表
* */

import sun.reflect.generics.tree.Tree;

public class Flatten {
//    TreeNode last=null;
//    public void flatten(TreeNode root) {
//        if(root==null){
//            return;
//        }
//        flatten(root.right);
//        flatten(root.left);
//        root.right=last;
//        root.left=null;
//        last=root;
//    }
    public void flatten(TreeNode root) {
        while(root!=null){
            if(root.left==null){
                root=root.right;
            }else {
                // 找左子树的最右边节点
                TreeNode pre=root.left;
                while(pre.right!=null){
                    pre=pre.right;
                }
                pre.right=root.right;
                root.right=root.left;
                root.left=null;
                // 考虑下一个节点
                root=root.right;
            }
        }
    }
}
